package org.basis.algorithm.list;

import org.basis.algorithm.list.common.ListNodeUtil;
import org.basis.algorithm.list.common.PairNode;
import org.basis.algorithm.list.common.SingleNode;

import java.util.Stack;

/**
 * 链表反转
 * PriorityQueue 要求里面的元素必须实现了Comparable接口，或者new PriorityQueue的时候传入比较器，用于比较里面元素的大小
 * PriorityQueue 实现原理是使用的堆结构
 *
 * @author Mr_wenpan@163.com 2021/12/08 17:01
 */
public class ListInversion {

    public static void main(String[] args) {
        testReverse();
        PairNode<Integer> pairHead = ListNodeUtil.generateIntegerPairList(20, 50, false);
        ListNodeUtil.printPairList(pairHead);
        PairNode<Integer> newPairHead = reversePair(pairHead);
        ListNodeUtil.printPairList(newPairHead);

        SingleNode<Integer> singleNode = ListNodeUtil.generateIntegerSingleList(20, 30, true);
        ListNodeUtil.printSingleList(singleNode);
        SingleNode<Integer> singleNode1 = reverseSingleByStack(singleNode);
        ListNodeUtil.printSingleList(singleNode1);
    }

    /**
     * 使用对数器来验证算法
     */
    private static void testReverse() {
        final int num = 10000;
        // 使用对数器的方式来验证算法的正确性

        // 单链表反转
        for (int i = 0; i < num; i++) {
            SingleNode<Integer> head = ListNodeUtil.generateIntegerSingleList(10, 20, true);
            SingleNode<Integer> newHead = reverseSingle(head);
            // 再次反转
            SingleNode<Integer> newHead2 = reverseSingle(newHead);
            if (!ListNodeUtil.isSingleListEquals(head, newHead2)) {
                ListNodeUtil.printSingleList(head);
                ListNodeUtil.printSingleList(newHead2);
                System.out.println("两个链表不相等，反转单向链表有问题");
                break;
            }
        }

        // 双向链表反转
        for (int i = 0; i < num; i++) {
            PairNode<Integer> pairHead = ListNodeUtil.generateIntegerPairList(20, 50, false);
            PairNode<Integer> newPairHead = reversePair(pairHead);
            // 再次反转
            PairNode<Integer> newPairHead2 = reversePair(newPairHead);
            if (!ListNodeUtil.isPairListEquals(pairHead, newPairHead2)) {
                ListNodeUtil.printPairList(pairHead);
                ListNodeUtil.printPairList(newPairHead2);
                System.out.println("两个链表不相等，反转双向链表有问题");
                break;
            }
        }
    }

    /**
     * 借助栈来反转链表
     */
    private static SingleNode<Integer> reverseSingleByStack(SingleNode<Integer> head) {
        if (head == null) {
            return null;
        }
        SingleNode<Integer> p = head;
        Stack<SingleNode<Integer>> stack = new Stack<>();
        // 先压栈
        while (p != null) {
            stack.push(p);
            p = p.next;
        }

        // 先弹一个元素
        SingleNode<Integer> newHead = stack.pop();
        SingleNode<Integer> q = newHead;
        while (!stack.isEmpty()) {
            q.next = stack.pop();
            q = q.next;
        }

        // 栈中最后一个元素的next需要置为空
        q.next = null;

        return newHead;
    }

    /**
     * 单链表反转
     */
    private static SingleNode<Integer> reverseSingle(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 暂存前一个节点
        SingleNode<Integer> pre = null;
        SingleNode<Integer> cur = head;
        // 暂存下一个节点
        SingleNode<Integer> next = head.next;
        while (cur != null) {
            // 指向前一个节点
            cur.next = pre;
            // 指针移动
            pre = cur;
            cur = next;
            next = cur == null ? null : cur.next;
        }

        // 返回反转后的链表头节点
        return pre;
    }

    /**
     * 双向链表反转
     */
    private static PairNode<Integer> reversePair(PairNode<Integer> head) {
        if (head == null || head.next == null) {
            return head;
        }
        PairNode<Integer> pre = null;
        PairNode<Integer> cur = head;
        PairNode<Integer> next = head.next;

        while (cur != null) {
            cur.next = pre;
            cur.last = next;
            pre = cur;
            cur = next;
            next = next == null ? null : next.next;
        }
        // 返回新的头节点
        return pre;
    }
}
